\documentclass{ctexart}
 \usepackage{listings}
 \usepackage{color}
 \usepackage{graphicx}

 \pagestyle{headings}
 
\title{作业3报告}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=-1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{设计思路}
采用递归的思路，首先根据条件语句找到一个处于k1,k2范围内的节点，然后通过类似于中序遍历的操作，先将节点左子树在范围内的值从小到大输出，再输出当前节点的值，最后输出右子树范围内的值。
\begin{lstlisting}
public:
    BinaryNode *getroot()
	{
	    return root;
	}
    void rangesearch(BinaryNode * t,const Comparable &k1,const Comparable &k2)
    {
	 if(k1>k2)
	     throw IllegalArgumentException{ };
	if(t!=nullptr)
	{
	    if(t->element<k1)
	    {
		rangesearch(t->right,k1,k2);
		return;
	    }
	    if(t->element>k2)
	    {
		rangesearch(t->left,k1,k2);
		return;
	    }
            if(t->element!=k1)
	        rangesearch(t->left,k1,k2);
	    cout<<' '<<t->element;
           if(t->element!=k2)     
	       rangesearch(t->right,k1,k2);
	}	
    }
\end{lstlisting}
\section{理论分析}
下面计算该函数的平均运行时间界。根据设计思路，首先要找到第一个处于k1,k2范围内的值，而二叉搜索树的平均深度为log N，所以大约有log N个不在k1,k2范围内的节点递归调用了rangesearch()函数，时间开销为O(log N)。随后，在当前节点周围有处于k1,k2范围内的K个值要输出。可以想像最极端的情况下，二叉树不平衡，这一步的时间甚至可以是O(N)，但计算运行时间平均界，因此可以近似地认为二叉树是平衡的。此时约有K个节点递归调用rangesearch()函数，其中K－1个节点在k1,k2范围内，有可以忽略的少数节点不在范围内，因此平均开销为O(K)。所以平均运行时间界为O(K+log N)。
\section{数值结果分析}
\begin{figure}[htb]
  \centering{\includegraphics[width=12cm]  {pic/测试结果.png}}
  \caption{\label{运行时间}}
\end{figure}
在main()中创建了两个二叉搜索树t1,t2用于测试 。t1中有256个数，t2中有66536个数，分别查找t1中的30个数，t2中的60个数。由理论分析可知，运行时间界为O(log N)，此时t2的查找时间约为t1的两倍。 多次测试的数值结果也证实了这一点，上图为其中一次测试结果。其中第一次函数调用，由于冷启动的原因，耗时过久，因此将其排除。综上，理论分析得到数值分析的证实。
下面是测试主函数代码，其中函数createbst(int \_size)用于创建一个节点个数为\_size的随机打乱后可视为平衡的二叉搜索树。
\begin{lstlisting}
int main(int argc,char *argv[])
{
    clock_t start,end;
    BinarySearchTree<int> t1=createbst(256);
    BinarySearchTree<int> t2=createbst(65536);

    start=clock();
    t1.rangesearch(t1.getroot(),101,130);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;

    start=clock();
    t1.rangesearch(t1.getroot(),101,130);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;
    
    start=clock();
    t2.rangesearch(t2.getroot(),201,260);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;

    return 0;
}
\end{lstlisting}
\end{document}
